package genetic.q2;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
import java.util.Vector;

public abstract class PuzzlePhenotype {

	public abstract double fitness(PuzzleGenotype g);
	public abstract PuzzleGenotype createRandomInstance();
	public abstract PuzzleGenotype[] crossover(PuzzleGenotype g1, PuzzleGenotype g2);
	public abstract PuzzleGenotype mutate(PuzzleGenotype g, double Pm);
	public abstract List<PuzzleGenotype> getMatingPool(List<PuzzleGenotype> population, int populationSize);
	public abstract void updateFitness(List<PuzzleGenotype> population);
	public abstract List<PuzzleGenotype> getInitialPopulation(int populationSize);

	public List<PuzzleGenotype> getInitialRandomPopulation(int size){
		List<PuzzleGenotype> population = new LinkedList<PuzzleGenotype>();
		for (int i = 0; i < size; i++) {
			population.add(createRandomInstance());
		}
		return population;
	}

	// permutation operators
	protected int[] getRandomIntString(int size, int offset){
		int[] ans = new int[size];
		Vector<Integer> tmp = new Vector<Integer>();
		for (int i=1; i<size+1; i++){
			tmp.add(i+offset);
		}
		int index = 0;
		while (!tmp.isEmpty()){
			int random = (int)(Math.random()*(double)tmp.size());
			ans[index] = tmp.remove(random);
			index++;
		}
		return ans;
	}

	public int[] getRandomIntString(int size, int min, int max){
		int[] ans = new int[size];
		for (int i=0; i<size; i++){
			ans[i] = (int)(Math.random()*(max-min+1)+min);
		}
		return ans;
	}

	protected int[][] pmxCrossover(PuzzleGenotype g1, PuzzleGenotype g2){
		int[] p1 = g1.getIntString();
		int[] p2 = g2.getIntString();
		int[][] kids = new int[2][p1.length];
		int[] rand;
		if(Math.random()<0.3)
			rand = getRandomPair(p1.length);
		else
			rand = getPairByAid2(g1);
		Set<Integer> tmp1 = new TreeSet<Integer>();
		Set<Integer> tmp2 = new TreeSet<Integer>();
		if(rand[1] < rand[0]){
			rand[1]=rand[1]+p1.length;
		}
		int len = p1.length;
		for (int i=rand[0]; i<=rand[1]; i++){
			kids[0][i%len] = p1[i%len];
			tmp1.add(p1[i%len]);
			kids[1][i%len] = p2[i%len];
			tmp2.add(p2[i%len]);
		}

		for (int i=rand[0]; i<=rand[1]; i++){
			if (!tmp1.contains(p2[i%len])){
				//element p2[i] wasnt copied
				int newplace = i%len;
				while (tmp1.contains(kids[0][newplace])){
					newplace = indexOf(p2, p1[newplace]);
				}
				kids[0][newplace] = p2[i%len];
				tmp1.add(p2[i%len]);
			}

			if (!tmp2.contains(p1[i%len])){
				//element p1[i] wasnt copied
				int newplace = i%len;
				while (tmp2.contains(kids[1][newplace])){
					newplace = indexOf(p1, p2[newplace]);
				}
				kids[1][newplace] = p1[i%len];
				tmp2.add(p1[i%len]);
			}
		}

		for (int i=0; i<p1.length; i++){
			if (!tmp1.contains(p2[i])){
				kids[0][i] = p2[i];
			}
			if (!tmp2.contains(p1[i])){
				kids[1][i] = p1[i];
			}
		}
		return kids;
	}

	protected int[] inverseMutation(PuzzleGenotype gen){
		int[] org = gen.getIntString();
		int[] ans = Arrays.copyOf(org, org.length);
		int[] rand = null;
		if (Math.random()<0.3){
			rand = getRandomPair(org.length);
		} else {
			rand = getPairByAid2(gen);
		}
		for (int i=rand[0] ; i<=rand[1]; i++){
			ans [i] = org[rand[1]+rand[0]-i];
		}
		return ans;
	}


	protected int[] getPairByAid(PuzzleGenotype g1) {
		int[] ans = new int[2];
		int f=0;
		double fd = 1;
		int s=1;
		double sd = 1;
		int best = 0;
		double bd = 0;
		double[] aid = g1.getAid();
		for(int i=0;i<aid.length;i++){
			if(aid[i] > bd){
				best = i;
				bd = aid[i];
			}
			if(aid[i] < fd){
				s=f;
				sd=fd;
				f=i;
				fd=aid[i];
			}
			else if(aid[i] < sd){
				s=i;
				sd=aid[i];
			}
		}
		if (f < s){
			if (f < best && best < s){
				ans[0] = f;
				ans[1] = s;
			}else{
				ans[0] = s;
				ans[1] = f;				
			}
		}else{
			if (s < best && best < f){
				ans[0] = s;
				ans[1] = f;
			}else{
				ans[0] = f;
				ans[1] = s;				
			}
		}
		return ans;
	}


	protected int[] getPairByAid2(PuzzleGenotype g1) {
		int[] ans = new int[2];
		double[] aid = g1.getAid();
		double tmp1 = 0;
		for (int i=0 ; i<aid.length; i++){
			tmp1+= aid[i];
		}
		double rand = Math.random()*tmp1;
		double rand2 = Math.random()*tmp1;
		for (int i=0; i<aid.length; i++){
			if (rand>0){
				rand = rand - aid[i];
				if (rand<=0){
					ans[0] = i;
				}
			}
			if (rand2>0){
				rand2 = rand - aid[i];
				if (rand2<=0){
					ans[1] = i;
				}
			}
		}
		if (ans[0] > ans[1]){
			int tmp = ans[0];
			ans[0] = ans[1];
			ans[1] = tmp;
		} else if (ans[0] == ans[1]){
//			System.out.print("BOO " + ans[0]);
			return getRandomPair(g1.getIntString().length);
		}
		int max1=(ans[0]+1) % aid.length , max2=(ans[1]+1) % aid.length;
		for (int i=ans[0]; i<ans[1]; i++){
			if (aid[i] > aid[max1]){
				max1 = i;
			}
		}
		
		for (int i=ans[1]; i<ans[0] + aid.length; i++){
			if (aid[i % aid.length] > aid[max2]){
				max2 = i % aid.length;
			}
		}
		
		if (max1 > max2){
			int tmp = ans[0];
			ans[0] = ans[1];
			ans[1] = tmp;
		}
		return ans;
	}

	//helping functions
	private int indexOf(int[] arr, int num){
		for (int i=0; i<arr.length; i++){
			if (arr[i] == num) return i;
		}
		return -1;
	}

	protected int[] getRandomPair(int size){
		return getRandomPair(size, 1, size);
	}

	protected int[] getRandomPair(int size, int minoffset){
		return getRandomPair(size, minoffset, size);
	}

	protected int[] getRandomPair(int size, int minoffset, int maxoffset){
		int rand1 = (int)(Math.random()*(double)(size-minoffset));
		int rand2 = (int)(Math.random()*(double)(Math.min(maxoffset, size-(rand1+minoffset)))) + rand1+minoffset;
		return new int[]{rand1, rand2};
	}

	protected List<PuzzleGenotype> getMatingPoolTournamentSelection(List<PuzzleGenotype> population, int populationSize, int tournamentSize, int numWinners, double p){
		List<PuzzleGenotype> matingPool = new LinkedList<PuzzleGenotype>();

		while (matingPool.size()<populationSize){
			Vector<PuzzleGenotype> tournament = new Vector<PuzzleGenotype>();
			for (int i=0; i<tournamentSize; i++){
				int index = (int)(Math.random()*(double)populationSize);
				tournament.add(population.get(index));
			}

			Collections.sort(tournament, new Comparator<PuzzleGenotype>(){
				@Override
				public int compare(PuzzleGenotype o1, PuzzleGenotype o2) {
					if (fitness(o1) < fitness(o2)){
						return -1;
					} else if (fitness(o1) > fitness(o2)){
						return 1;
					} else {
						return 0;
					}
				}
			});

			for (int i=0; i<numWinners; i++){
				for (int j=0; j<tournament.size(); j++){
					if (Math.random()<p || j == tournament.size()-1){
						matingPool.add(tournament.remove(j));
						break;
					}
				}
			}
		}
		Collections.shuffle(matingPool);
		return matingPool;
	}

	public List<PuzzleGenotype> elitist(List<PuzzleGenotype> population,
			int populationSize, int elitism) {
		List<PuzzleGenotype> ans = new LinkedList<PuzzleGenotype>();

		double[][] tmp = new double[populationSize][2];
		for(int i=0; i<populationSize; i++){
			tmp[i][0]=i;
			tmp[i][1]=fitness(population.get(i));
		}
		mergeSort(tmp);
		for(int i=0; i<elitism; i++){
			PuzzleGenotype g = population.get((int)tmp[tmp.length-(1+i)][0]).clone();
			ans.add(g);
		}
		return ans;
	}

	/**
	 * Mergesort algorithm.
	 * @param a an array of Comparable items.
	 */
	public static void mergeSort( double [][] a ) {
		double [][] tmpArray = new double[ a.length ][2];
		mergeSort( a, tmpArray, 0, a.length - 1 );
	}

	/**
	 * Internal method that makes recursive calls.
	 * @param a an array of Comparable items.
	 * @param tmpArray an array to place the merged result.
	 * @param left the left-most index of the subarray.
	 * @param right the right-most index of the subarray.
	 */
	private static void mergeSort( double [][] a, double [][] tmpArray,
			int left, int right ) {
		if( left < right ) {
			int center = ( left + right ) / 2;
			mergeSort( a, tmpArray, left, center );
			mergeSort( a, tmpArray, center + 1, right );
			merge( a, tmpArray, left, center + 1, right );
		}
	}

	/**
	 * Internal method that merges two sorted halves of a subarray.
	 * @param a an array of Comparable items.
	 * @param tmpArray an array to place the merged result.
	 * @param leftPos the left-most index of the subarray.
	 * @param rightPos the index of the start of the second half.
	 * @param rightEnd the right-most index of the subarray.
	 */
	private static void merge( double [][] a, double [][] tmpArray,
			int leftPos, int rightPos, int rightEnd ) {
		int leftEnd = rightPos - 1;
		int tmpPos = leftPos;
		int numElements = rightEnd - leftPos + 1;

		// Main loop
		while( leftPos <= leftEnd && rightPos <= rightEnd )
			if( a[leftPos][1]< a[rightPos][1] ){
				tmpArray[tmpPos][0] = a[leftPos][0];
				tmpArray[tmpPos][1] = a[leftPos][1];
				tmpPos++;
				leftPos++;
			}
			else{
				tmpArray[tmpPos][0] = a[rightPos][0];
				tmpArray[tmpPos][1] = a[rightPos][1];
				tmpPos++;
				rightPos++;
			}
		while( leftPos <= leftEnd ){    // Copy rest of first half
			tmpArray[ tmpPos ][0] = a[ leftPos ][0];
			tmpArray[ tmpPos ][1] = a[ leftPos ][1];
			tmpPos++;
			leftPos++;
		}
		while( rightPos <= rightEnd ){  // Copy rest of right half
			tmpArray[ tmpPos ][0] = a[ rightPos ][0];
			tmpArray[ tmpPos ][1] = a[ rightPos ][1];
			tmpPos++;
			rightPos++;
		}
		// Copy tmpArray back
		for( int i = 0; i < numElements; i++, rightEnd-- ){
			a[ rightEnd ][0] = tmpArray[ rightEnd ][0];
			a[ rightEnd ][1] = tmpArray[ rightEnd ][1];
		}
	}

}
